class Solution {
public:
    /**
     * lru design
     * @param operators int整型vector<vector<>> the ops
     * @param k int整型 the k
     * @return int整型vector
     */
    /*
    LRU最近最少使用，使用双向链表和哈希实现，数据的格式为（key,value）
    list存key
    hash的first存key,second存一个pair(value,iterator);iterator指向list中的结点
    get(int key)表示获取数据，每访问一次，如果存在，就将数据移动到链表的最右边，
                同时更改哈希表中迭代器的指向。
    set(int key,int value)表示插入数据。
    caes1:如果待插入的数据中已经存在了，只需要修改value即可，
    case2:如果不存在，而且容量足够，将数据插入到链表的最右边，
           同时创建哈希结点，让它的结点指向该链表的最右结点
    case3:容量不够，删掉双链表的最前面的结点，同时删掉该数据所对应的哈希表结点。
    */
   //list存key
    list<int>mylist;
    //哈希表的first存key ,second存pair(value,itrtator)
    unordered_map<int, pair<int, list<int>::iterator>>hashmap;
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
       vector<int>ans;
       for(int i=0;i<operators.size();i++)
       {    if(operators[i][0]==1)
               set(operators[i][1],operators[i][2],k);
            else if(operators[i][0]==2)
               ans.push_back(get(operators[i][1]));
       }
        return ans;
    }
    void insert(int key,int value)
    {
        mylist.push_back(key);
        hashmap[key]=make_pair(value, --mylist.end());
    }
    int get(int key)
    {
        auto it=hashmap.find(key); //it是哈希表的迭代器
        if(it!=hashmap.end())
        {
            mylist.erase(it->second.second); //将该结点移动链表的最右边
            mylist.push_back(key);
            hashmap[key].second=(--mylist.end());//更改迭代器的指向
            return it->second.first;
        }
        return -1;
    }
    void set(int key,int value,int k)
    {
        if(get(key)!=-1) //原list中有key
        {
            hashmap[key].first=value;
            return;
        }
        if(hashmap.size()<k)
            insert(key, value);
        else //内存不足
        {
            int removekey=mylist.front();
            mylist.pop_front();
            hashmap.erase(removekey);
            insert(key, value);
        }
    }
};